CF1270D Strange Device

---

思维题，交互题，现场脑抽没有打出脑子中的正确算法，导致排名并不是很高，直接导致了新年上紫失败

---

题意：

给出$n$和$k$，让你求$m$

其中$n$表示$n$个数，$k$表示每次你可以询问的数的个数，$m$是对于你的询问，交互器返回的是你所询问$k$个数中的第$m$小数

特别的，n个数互不相同

规定询问格式为：

$k$个$\in[1,n]$互不相同的数，表示下标

规定交互器回答你的询问的格式为：

两个数$x$和$y$，其中$x$是这$k$个数中第$m$小数的下标，$y=a_x$

---

题解：

题目给出了$n$个数，但其实我们只需要用到$k+1$个数

为了方便解释，规定$ask(x) [x\in[1,k+1]]$表示一次从$1$到$k+1$的询问，但不包括下标$x$

先$ask(k+1)$，记返回的$x$为$pos$，$y$为$p$

再$ask(pos)$，记返回的$y$为$q$

通过两次询问我们可以得出$a_{pos}$和$a_{k+1}$大小关系

判断方法为：若$q>p$则$a_{k+1}>a_{pos}$，否则$a_{k+1}<a_{pos}$

为什么呢？可以类比一下平均数，更换一个数就是在修改平均数的权重

然后再做$k-1$次询问$ask(x) [x\in[1,k] | x\neq pos]$

记每次询问的到的$y$为$num$，前$k$个数中比$p$小的数有$cnt$个

根据上文得出的$a_{pos}$和$a_{k+1}$大小关系进行如下分类讨论：

---

• $a_{pos}<a_{k+1}$

此时若$num=p$则说明只是在比$p$小的数里做了个交换，$cnt+1$

• $a_{pos}>a_{k+1}$

此时若$num!=p$则说明是从比$p$小的数里选了个数做交换，$cnt+1$

---

最后的答案$m=cnt+1$

---

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

int n,k,ka,kb,pa,pb,ans,op;

void print(int x){
    printf("? ");
    for(int i=1;i<=k+1;i++) if(i^x) printf("%d ",i);
    puts("");
    cout.flush();
}

signed main(){
    read(n);read(k);
    print(k+1);
    read(ka);read(kb);
    print(ka);
    read(pa);read(pb);
    op=pb>kb;
    for(int i=1,x,y;i<=k;i++) if(i^ka){
        print(i);
        read(x);read(y);
        if(!op){
            if(y==kb) ans++;
        }
        else{
            if(y^kb) ans++;
        }
    }
    printf("! %d\n",ans+1);
}